<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    class HashTable {
      constructor () {
        this.storage = []
        this.count = 0
        this.size = 7
        this.isScaling = false
      }
      // 1.哈希函数, 只获取到hashCode
      hashFunc (key, size = this.size) {
        let hashCode = 0
        for (let i = 0; i < key.length; i++) {
          hashCode = 37 * hashCode + key.charCodeAt(i)
        }
        return hashCode % size
      }
      // 2. 加入数据&修改数据
      put (key, value) {
        if (typeof(key) !== 'string' || !value) return console.error('请传入正确的key')
        // 获取hash的Index
        const index = this.hashFunc(key, this.size)
        let flag = true
        // 获取哈希表的'桶'
        if (!this.storage[index]) this.storage[index] = []
        const bucket = this.storage[index]
          // forEach()`无法在所有元素都传递给调用的函数之前终止遍历
        for (let i = 0; i < bucket.length; i++) {
          const tuple = bucket[i]
          if (tuple[0] === key) {
            tuple[1] = value
            // console.log(element[0], key)
            // console.log(11111)
            return true
          }
        }
        // bucket.forEach(element => {
        //   if (element[0] === key) {
        //     element[1] = value
        //     flag = false
        //     // console.log(element[0], key)
        //     // console.log(11111)
        //     return bucket
        //   }
        // })
        // if (!flag) return bucket
        // 若无修改情况则插入数据
        bucket.push([key, value])
        this.count++
        this.checkResize()
        // console.log('push')
        return true
      }
      // 3. 删除元素
      remove (key) {
        if (typeof(key) !== 'string') return console.error('请传入正确的key')
        // 获取hash的Index
        const index = this.hashFunc(key, this.size)
        // 获取哈希表的'桶'
        const bucket = this.storage[index]
        if (!bucket) return console.log('找不到该值')
        for (let i = 0; i < bucket.length; i++) {
          let tuple = bucket[i]
          if (tuple[0] === key) {
            bucket.splice(i, 1)
            this.count--
            this.checkResize()
            return tuple
          }
        }
        return '没有找到要删除的元素'
      }
      // 4. 获取元素
      get (key) {
        if (typeof(key) !== 'string') return console.error('请传入正确的key')
        const index = this.hashFunc(key)
        let bucket = this.storage[index]
        for (let i = 0; i < bucket.length; i++) {
          const tuple = bucket[i]
          if (tuple[0] === key) {
            return tuple[1]
          }
        }
        return '没有找到元素'
      }
      // 5. 扩容
      checkResize () {
        const loadFactor = this.count / this.size
        // console.log(loadFactor)
        if (!((0.25 > loadFactor && this.size !== 7 ) || loadFactor > 0.75) || this.isScaling) return
        
        // 表示正在收容扩容
        this.isScaling = true
        // 如果是小于0.25则缩小容器
        let isShrink = false
        if (loadFactor < 0.25) isShrink = true
        let resultNum = this.size
        // 根据缩小还是放大来乘2或者除以2
        isShrink ? resultNum = Math.ceil(this.size / 2) : resultNum = Math.floor(this.size * 2)
        // 直到选到质数为止
        while (this.isPrime(resultNum) === false) {
          isShrink ? resultNum-- : resultNum++
        }
        console.log(resultNum, '需要扩容或者缩容')
        // 重置操作
        const oldStorage = this.storage
        this.count = 0
        this.size = resultNum
        this.storage = []
        // 扩容操作
        oldStorage.forEach(bucket => {
          if (bucket) {
            bucket.forEach(tuple => {
              this.put(tuple[0], tuple[1])
            })
          }
        })
        // 收容结束
        this.isScaling = false
      }
      // -----------------其他方法的实现--------------------
      isEmpty () {
        return this.count === 0
      }
      isPrime (num) {
        if (!num || typeof num !== 'number') {
          return console.log('请输入数字')
          return true
        }
        // if (num === 2 || num === 3) return true
        for (let i = 2; i <= Math.sqrt(num); i++) {
          if (num % i === 0) {
            return false
          }
        }
        return true
      }
    }
    const test1 = new HashTable()
    console.log(test1.put('aaaaa', 'aaa'))
    console.log(test1.put('aaaap', 'aaa'))
    console.log(test1.put('aaaaz', 'aaa'))
    console.log(test1.put('aaaah', 'aaa'))
    console.log(test1.put('aaaas', 'aaa'))
    console.log(test1.put('aaaat', 'aaa'))
    console.log(test1.put('aaaaq', 'aaa'))
    console.log(test1.put('aaaah', 'bbb'))
    console.log(test1.remove('aaaas'))
    console.log(test1.remove('aaaat'))
    console.log(test1.remove('aaaaq'))
    console.log(test1.remove('aaaah'))
    console.log(test1.put('aaaaa', '这是我修改了的值'))
    // console.log(test1.get('aaaaa'))
    console.log(test1.storage)
  </script>
</body>
</html>